Marge empirique de \(f:\mathcal X\to{\Bbb R}\)
mesurable
Quantité définie avec \(\mathcal Y=\{-1,1\}\) (
Problème de reconnaissance des formes) par : $$\hat m_l(f):=\inf_{1\leqslant i\leqslant l}Y_if(X_i)$$
- intérêt : les données d'apprentissage sont toutes correctement classées sans ambigüité si et seulement si \(\hat m_l(f)\gt 0\)
- on a avec probabilité \(1-4e^{-2t^2}\) : $${\Bbb P}(Yf(X)\leqslant 0)\leqslant\inf_{\delta\in[0,\delta_0[}\left(\frac1l\sum^l_{i=1}\Bbb 1_{Y_if(X_i)\leqslant\delta}+\frac{4\hat R_l({\mathcal F})}\delta+3\frac{t+\sqrt{\log(\log_2(2\delta_0/\delta))} }{\sqrt l}\right)$$(Complexité empirique de Rademacher)
- corollaire : $${\Bbb P}(Tf(X)\leqslant0)\leqslant\frac{4\hat R_l({\mathcal F})}{\hat m_l(f)\land\delta_0}+3\frac{t+\sqrt{\log\log_2\frac{2\delta_0}{\hat m_l(f)\land\delta_0}} }{\sqrt l}$$
- cette inégalité est surprenante : le terme de droite décroît avec la marge \(\to\) si la marge est grande, une petite perturbation sur les données ne va pas changer le signe de \(f\), et la frontière \(\{f(x)=0\}\) est sans doute mieux placée entre les deux
- on veut donc choisir \(f\) qui maximise la marge
